home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / doc.lha / doc.doc / multiple.doc < prev    next >
Text File  |  1992-09-25  |  41KB  |  1,098 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11. ___________________________________________________________________
  12.  
  13.                                    Multiple Inheritance
  14.                                    in Object-Oriented
  15.                                    Attribute Grammars
  16.  
  17.                                    J. Grosch
  18.  
  19.  
  20. ___________________________________________________________________
  21.  
  22.  
  23.  
  24.  
  25.  
  26.  
  27.  
  28.  
  29.  
  30.  
  31.  
  32.  
  33.  
  34.  
  35.  
  36.  
  37.  
  38.  
  39.  
  40.  
  41.  
  42.  
  43.  
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50. ___________________________________________________________________
  51.                                    GESELLSCHAFT FUeR MATHEMATIK
  52.                                    UND DATENVERARBEITUNG MBH
  53.  
  54.                                    FORSCHUNGSSTELLE FUeR
  55.                                    PROGRAMMSTRUKTUREN
  56.                                    AN DER UNIVERSITAeT KARLSRUHE
  57. ___________________________________________________________________
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75.                                    Project
  76.  
  77.                              Compiler Generation
  78.  
  79.          ___________________________________________________________
  80.  
  81.           Multiple Inheritance in Object-Oriented Attribute Grammars
  82.  
  83.  
  84.                                  Josef Grosch
  85.  
  86.  
  87.                                 Feb. 25, 1992
  88.  
  89.          ___________________________________________________________
  90.  
  91.  
  92.                                 Report No. 28
  93.  
  94.  
  95.                              Copyright c 1992 GMD
  96.  
  97.  
  98.             Gesellschaft fuer Mathematik und Datenverarbeitung mbH
  99.                 Forschungsstelle an der Universitaet Karlsruhe
  100.                           Vincenz-Priesznitz-Str. 1
  101.                                D-7500 Karlsruhe
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.                                                                              1
  135.  
  136.  
  137.           Multiple Inheritance in Object-Oriented Attribute Grammars
  138.  
  139.  
  140.                                  Josef Grosch
  141.               GMD Forschungsstelle an der Universitaet Karlsruhe
  142.              Vincenz-Priesznitz-Str. 1, D-7500 Karlsruhe, Germany
  143.                            grosch@karlsruhe.gmd.de
  144.  
  145.  
  146.  
  147. Abstract   Object-oriented attribute grammars are  a  promising  notation  for
  148. language  specifications.  They have similar benefits as object-orientation in
  149. the area of programming languages. They support a compact and  flexible  style
  150. for language specifications. Existing definitions can be easily reused as well
  151. as the associated default behaviour.  New  definitions  can  be  derived  from
  152. existing  ones  by  specialization.  While  previous approaches have been res-
  153. tricted to single inheritance this  paper  defines  object-oriented  attribute
  154. grammars with multiple inheritance. A system has been developed that processes
  155. those attribute grammars. We describe an example that  uses  multiple  inheri-
  156. tance and compare the terminology and concepts of related areas.
  157.  
  158. Keywords   attribute grammar, object-orientation, multiple inheritance
  159.  
  160. 1.  Introduction
  161.  
  162. Object-oriented attribute grammars have been introduced by several authors (e.
  163. g.  [Gro90a, Hed89]) as a promising notation for attribute grammars.  An over-
  164. view of the current state of the art in this area is given  in  [Kos91].   The
  165. benefits are comparable to those of object-oriented programming languages.  It
  166. is a concise notation and flexible notation for language specifications.   The
  167. reuse  of  existing definitions is supported by the possibility to specify new
  168. definitions as extensions or specializations of existing ones.   The  duplica-
  169. tion of information is avoided because common parts can be "factored out".
  170.  
  171.      While the main building blocks of object-oriented  programming  languages
  172. are  classes,  the  nonterminals  play  this part in object-oriented attribute
  173. grammars. More precisely, the notions nonterminal and production rule are uni-
  174. fied. This means that there is exactly one production rule for every nontermi-
  175. nal. Additionally, a relation between nonterminals is specified,  for  example
  176. using chain rules, which describes a subtype relation or class hierarchy among
  177. the nonterminals. This subtype relation serves for  two  purposes.  First,  it
  178. allows to derive several different strings from one nonterminal because a non-
  179. terminal may be replaced by a right-hand side corresponding to  a  nonterminal
  180. that  is a subtype of the replaced one. Second, the subtype relation describes
  181. the path for inheritance among the nonterminals. The items that are subject to
  182. inheritance  are  right-hand side elements, attributes, and attribute computa-
  183. tions.  Inherited attribute computations may be overwritten in the subtype  by
  184. giving different computations for the same attributes.
  185.  
  186.      Before we  proceed  we  have  to  clarify  the  terminology:  Originally,
  187. context-free grammars as well as attribute grammars are derivation systems for
  188. strings. In this paper we are interested  in  the  specification  of  semantic
  189. analysis  which is based on an abstract syntax tree. Therefore we use grammars
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.                                                                              2
  201.  
  202.  
  203. to describe the structure of trees instead of strings.
  204.  
  205. In order to avoid confusion between the terms  class,  nonterminal,  terminal,
  206. and  (sub)type we will use the term node type to cover all those meanings. The
  207. term node type is motivated through a realistic description of what is happen-
  208. ing:  The node types specify the structure of the nodes of the abstract syntax
  209. tree.
  210.  
  211. The attributes in attribute grammars are usually classified as synthesized and
  212. inherited.   Following  Hedin  [Hed89]  we  use  the  term ancestral attribute
  213. instead of the standard inherited attribute since we use the term inherited in
  214. the object-oriented sense.
  215.  
  216.      There is one problem that  arises  especially  from  the  combination  of
  217. ancestral  attributes and inheritance. Let A, B, and C be node types and let B
  218. be a subtype of A (B  A) having one ancestral attribute x. If  the  right-hand
  219. side  of C contains an A, we have to know whether to compute the attribute A.x
  220. or not. The static type is A, but the dynamic type can be any subtype, that is
  221. A  or  B. If it is B we have to compute A.x, if it is A we may not compute it.
  222. The notions node type, subtype, and right-hand side are defined in section 2.
  223.  
  224.      There are several solutions to this problem. First, one can restrict  the
  225. definition  of  ancestral attributes to top level node types, only. This makes
  226. the reuse of existing node types very hard in particular in  combination  with
  227. multiple inheritance.
  228.  
  229.      Second, one could use a dynamic dispatch  technique  which  inspects  the
  230. dynamic  type  of the right-hand side child and decides during runtime whether
  231. to compute A.x or not. This solution is rather inefficient because of its run-
  232. time overhead.
  233.  
  234.      Most existing systems therefore allow single inheritance, only, with  the
  235. additional  restriction  that  ancestral  attributes have to be defined at top
  236. level node types. The last restriction is not severe because it somehow  coin-
  237. cides  in  a  natural  way  with the style of usual attribute grammars.  Hedin
  238. [Hed89] follows this argumentation and calls object-oriented  attribute  gram-
  239. mars having the above problem not well formed.
  240.  
  241.      This paper introduces a third solution to the above mentioned problem. It
  242. allows  for  a  restricted  form of multiple inheritance and still retains the
  243. capability to decide at generation time which ancestral attributes have to  be
  244. computed. Attribute evaluators can still be implemented efficiently as dynamic
  245. dispatch is avoided.
  246.  
  247.      In section 2 we formally define object-oriented attribute  grammars  with
  248. single  inheritance.   Section  3  contains  two  simple examples using single
  249. inheritance.  Section 4 extends the definition  of  object-oriented  attribute
  250. grammars  to  multiple  inheritance.   Section 5 presents an elaborate example
  251. with multiple inheritance.  In section 6 we compare  our  approach  with  pure
  252. attribute grammars and with object-oriented programming in order to reveal the
  253. common properties as well  as  the  differences.   Section  7  summarizes  the
  254. results.
  255.  
  256.  
  257.  
  258.  
  259.  
  260.  
  261.  
  262.  
  263.  
  264.  
  265.                                                                              3
  266.  
  267.  
  268. 2.  Single Inheritance
  269.  
  270. This section formally defines  the  principles  of  object-oriented  attribute
  271. grammars  with  single  inheritance.   As starting point we shortly recall the
  272. traditional definition of attribute grammars [Knu68, Knu71].
  273.  
  274.      An attribute grammar is  an  extension  of  a  context-free  grammar.   A
  275. context-free grammar is denoted by G = (N, T, P, Z) where N is the set of non-
  276. terminals, T is the set of terminals, P is the set of productions, and Z  N is
  277. the start symbol, which cannot appear on the right-hand side of any production
  278. in P.  The set V = N U T is called the vocabulary.  Each production p   P  has
  279. the  form p: X -> A where X  N and A  V*.  The relation  (directly derives) is
  280. defined over strings in V* as follows: if p: X -> A, p   P,  @XC  V*,  @AC  V*
  281. then  @XC  @AC.   The  relation * is the transitive and reflexive closure of .
  282. The language L(G) is defined as L(G) = { w | Z * w }.
  283.  
  284.      An attribute grammar augments a context-free grammar  by  attributes  and
  285. attribute  computations. A set of attributes is associated with each symbol in
  286. V.  Attribute computations are added to every  production  describing  how  to
  287. compute  attribute  values  in the local context of a production.  This simple
  288. view of attribute grammars shall suffice for the scope of this paper.
  289.  
  290.      In general there can be several productions having the  same  nonterminal
  291. on  the  left-hand  side.  This allows for different derivations starting from
  292. one nonterminal. In object-oriented attribute grammars, one production is per-
  293. mitted  for  one left-hand side symbol, only.  This way the notions production
  294. and nonterminal (vocabulary respectively) are unified and are termed node type
  295. as  already mentioned. Several different derivations are made possible through
  296. the newly introduced subtype relation.
  297.  
  298.      An object-oriented attribute grammar is formally denoted by G = (N, T, A,
  299. C,  Z) where N is the set of nonterminals, T is the set of terminals, A is the
  300. set of attributes, C is the set of attribute computations, and Z is the  start
  301. symbol (Z  N).  The set NT = N U T is called the set of node types.  Each ele-
  302. ment n  NT is associated with a tuple n: (R, B, D,  S)  where  R  NT*  is  the
  303. right-hand side, B  A* is the set of attributes, D  C* is the set of attribute
  304. computations, and S  NT is the base type.
  305.  
  306.      The elements of NT induce a relation  (subtype) over NT  as  follows:  if
  307. n: (A, B, D, m)  NT  then  n   m.  m is called base or super type, n is called
  308. derived type or subtype.  The relation  is transitive: if n  m and m  o then n
  309.  o.
  310.  
  311.      The relation  (directly derives) is defined here only  for  the  context-
  312. free  or syntactic part of an object-oriented attribute grammar. There are two
  313. possibilities for derivations which are defined over strings in  NT*  as  fol-
  314. lows:
  315.  
  316.       if @niC  NT* andn1: (A1, B1, D1, n0)  NT,
  317.                n2: (A2, B2, D2, n1)  NT,
  318.                             . . .
  319.                ni: (Ai, Bi, Di, ni-1)  NT then @niC  @A1A2 . . . AiC.
  320.  
  321.  
  322.  
  323.  
  324.  
  325.  
  326.  
  327.  
  328.  
  329.  
  330.                                                                              4
  331.  
  332.  
  333.       if @nC  NT* and m  n then @nC  @mC.
  334.  
  335. We assume the existence of a predefined node  type  n0: (, , , -)  with  empty
  336. components.  In  a  direct derivation step, a node type can be replaced by its
  337. right-hand side (A1 . . . Ai) or by one of its  subtypes  (m).  All  replacing
  338. right-hand  sides  are  the union of right-hand sides according to the subtype
  339. hierarchy.  The relation * is the transitive and reflexive closure of  .   The
  340. language L(G) is defined as L(G) = { w | Z * w }.
  341.  
  342.      The subtype relation has the following properties: a  derived  node  type
  343. inherits  the  right-hand side, the attributes, and the attribute computations
  344. from its base type. As consequence of the transitive nature of this  relation,
  345. a  derived  type  inherits all the components from all base types according to
  346. the subtype hierarchy.  It may extend the set of inherited items  by  defining
  347. additional  right-hand  side  elements, attributes, or attribute computations.
  348. All accumulated right-hand side  elements  and  attributes  must  be  distinct
  349. because  they  are  united.  An  attribute  computation  for  an attribute may
  350. overwrite an inherited one.
  351.  
  352. 3.  Example
  353.  
  354. We implemented an attribute grammar system called ag based on  object-oriented
  355. attribute  grammars  which  is part of the Karlsruhe Toolbox for Compiler Con-
  356. struction [GrE90].  It supports the kinds of single and  multiple  inheritance
  357. described  in this paper.  The following examples of object-oriented attribute
  358. grammars with single inheritance are written in the specification language  of
  359. ag.   The  language  tries to adhere to the conventional style of context-free
  360. grammars as far as possible. It offers far more features for  practical  usage
  361. than  can  be  explained here. The interested reader is referred to the user's
  362. manual [Gro89].
  363.  
  364.      An attribute grammar is given in the form of  nested  node  type  defini-
  365. tions.  The nesting expresses the subtype hierarchy or the subtype relation. A
  366. node type definition consists of properties of the node  type  followed  by  a
  367. list  of  subtype  definitions  enclosed in angle brackets < >. The properties
  368. include the structural or syntactic definition  (right-hand  side),  attribute
  369. definitions, and attribute computations.
  370.  
  371.     Example 1:
  372.     Expr        = [Value: INTEGER]    { Value := 0; } <
  373.        Add      = Lop: Expr Rop: Expr { Value := Lop:Value + Rop:Value; } .
  374.        Sub      = Lop: Expr Rop: Expr { Value := Lop:Value - Rop:Value; } .
  375.        Const    = Integer             { Value := Integer:Value; } .
  376.     > .
  377.     Integer     = [Value: INTEGER] .
  378.  
  379.  
  380.      The example describes the evaluation of primitive expressions.  Attribute
  381. definitions  are given in brackets [ ]. The attribute Value is associated with
  382. all subtypes of Expr with a default computation "Value := 0;".  The  attribute
  383. computations  are written in curly brackets { }. The computations for the node
  384. types Add, Sub, and Const overwrite the computation given  in  the  base  type
  385.  
  386.  
  387.  
  388.  
  389.  
  390.  
  391.  
  392.  
  393.  
  394.  
  395.                                                                              5
  396.  
  397.  
  398. Expr.
  399.  
  400.      The structural or syntactic definition is given as  a  sequence  of  node
  401. type  names,  possibly  prefixed by a selector (Lop, Rop) allowing unambiguous
  402. access to the component structures.
  403.  
  404.     Example 2:
  405.     Stats       = <
  406.        NoStat   = .
  407.        Stat     = Next: Stats [Pos: tPosition] <
  408.           If    = Expr Then: Stats Else: Stats .
  409.           While = Expr Stats .
  410.           Call  = Actuals [Ident: tIdent] .
  411.        > .
  412.     > .
  413.  
  414.  
  415.      Example 2 describes a possibility for the specification of  the  abstract
  416. syntax  of  statement  sequences.  The  example  uses  the  node type Stats to
  417. describe a sequence and the node type Stat to describe various statements. The
  418. node  types  are related as subtypes showing a non-trivial subtype relation of
  419. nesting depth two. The subtype relation is: NoStat  Stats, Stat   Stats,  If
  420. Stat,  While    Stat,  Call  Stat.  In Example 2 the node types If, While, and
  421. Call inherit the child Next of type Stats and the attribute Pos from the  base
  422. type Stat.  They add their own children and attributes.
  423.  
  424. 4.  Multiple Inheritance
  425.  
  426. The problem with multiple inheritance mentioned in  the  introduction  can  be
  427. solved  if  we  distinguish two kinds of types: node types and abstract types.
  428. An abstract syntax tree is constructed only out of nodes whose type is a  node
  429. type - there are no nodes whose type is an abstract one.  While the node types
  430. describe production rules or tree nodes the abstract types describe concepts.
  431.  
  432.      An object-oriented attribute grammar with multiple  inheritance  is  for-
  433. mally  denoted  by  G  =  (N, T, K, A, C, Z). N, T, A, C, Z represent the same
  434. entities as in the single inheritance case. In particular the set NT = N  U  T
  435. represents the set of node types.  K is the set of abstract types.  Every ele-
  436. ment n  NT is now associated with a quintuple n: (R, B, D, S, L) where  R,  B,
  437. D,  and S are as before.  Every element k  K is associated with a quintuple k:
  438. (R, B, D, U, L) where U  K is the base type for the single inheritance mechan-
  439. ism and L  K* is the set of base types for the multiple inheritance mechanism.
  440. We have two inheritance  mechanisms  which  operate  simultaneously.  Multiple
  441. inheritance behaves similar as single inheritance: A subtype inherits all pro-
  442. perties (right-hand side, attributes, attribute  computations)  from  all  its
  443. base types.
  444.  
  445.      Why do we need two mechanisms for inheritance? We retained single inheri-
  446. tance for two reasons: First, it is good to be compatible with existing attri-
  447. bute grammars written in the single  inheritance  style.  Second,  the  single
  448. inheritance  notation  allows  to  adhere largely to the conventional style of
  449. writing context-free grammars.
  450.  
  451.  
  452.  
  453.  
  454.  
  455.  
  456.  
  457.  
  458.  
  459.  
  460.                                                                              6
  461.  
  462.  
  463.      The above definition for object-oriented grammars with  multiple  inheri-
  464. tance  distinguishes  two  levels  (see  Fig.  1).   The set of abstract types
  465. represents the abstract or conceptual level. These types  model  concepts  and
  466. properties  which  are  common to several node types or even to different pro-
  467. gramming languages. Abstract types are not used for nodes in the syntax  tree.
  468. The  set  of node types represents production rules of a context-free grammar.
  469. The node types describe the constructs of a programming language.  Node  types
  470. are used to classify the nodes in a syntax tree.
  471.  
  472.  
  473.            Fig. 1: Inheritance among abstract types and node types
  474.  
  475.  
  476.      The above definition of multiple inheritance allows multiple  inheritance
  477. among  abstract types and from abstract types to node types. Among node types,
  478. single inheritance is available, only. Ancestral attributes may be defined for
  479. all  abstract  types and for top level node types. With this restriction it is
  480. statically known for all children of all nodes  whether  ancestral  attributes
  481. have to be computed or not.
  482.  
  483. 5.  Example
  484.  
  485. In this section we present a rather elaborate example for  an  object-oriented
  486. attribute  grammar with multiple inheritance. The example is an excerpt from a
  487. specification of the demo language MiniLAX [Gro90b].  The  attribute  computa-
  488. tions are written directly in the implementation language which is Modula-2.
  489.  
  490.  
  491.  
  492.     Example 3:
  493.     MODULE SymbolTable
  494.     DECLS           := [Objects: tObjects THREAD OUT] <
  495.        NODECLS      := .
  496.        DECL         := Next: Decls IN [Ident: tIdent IN] [Pos: tPosition IN]
  497.                        { Next:ObjectsIn     := mObject (ObjectsIn, Ident);
  498.                          ObjectsOut         := Next:ObjectsOut;
  499.                          CHECK NOT IsDeclared (Ident, ObjectsIn)
  500.                          ==> Error ("identifier already declared", Pos);    } .
  501.     > .
  502.     ENV             := [Env: tEnv INH] .
  503.     USE   <- ENV    := [Ident: tIdent IN] [Object: tObjects SYN OUT]
  504.                        { Object             := Identify (Ident, Env);
  505.                          CHECK Object^.Kind # NoObject
  506.                          ==> Error ("identifier not declared", Pos);        } .
  507.     SCOPE <- ENV    := [Objects: tObjects SYN] [NewEnv: tEnv SYN]
  508.                        { Objects            := mNoObjects ();
  509.                          NewEnv             := mEnv (Objects, Env);         } .
  510.     END SymbolTable
  511.  
  512.  
  513.  
  514.  
  515.  
  516.  
  517.  
  518.  
  519.  
  520.  
  521.  
  522.  
  523.                                                                              7
  524.  
  525.  
  526.      The attribute grammar module in Example 3 describes  an  abstract  symbol
  527. table.   It  is  termed  abstract because we deal with entities called objects
  528. which are not further specified. The  symbol  table  handles  declarations  of
  529. objects,  applications (uses) of objects, and scopes. It does not specify what
  530. kind of objects are to be declared, where those objects are  used,  and  which
  531. constructs  are associated with scopes.  We use all upper-case names to denote
  532. abstract types.
  533.  
  534.      The first three definitions describe lists of  abstract  declarations.  A
  535. declaration  DECL  is  characterized  by  an  identifier  and a reference to a
  536. succeeding declaration.  The identifier is described by two  attributes  Ident
  537. and  Pos  holding an internal representation and a source position. The right-
  538. hand side child with the selector Next and the node type Decls refers  to  the
  539. succeeding declaration.
  540.  
  541.      A list of declarations (DECLS) is either empty (NODECLS) or  starts  with
  542. one  element  of type DECL.  The list has a threaded attribute called Objects.
  543. This threaded attribute actually stands for two  attributes  called  ObjectsIn
  544. and ObjectsOut.  The attribute computations given for DECL in curly brackets {
  545. } use this threaded attributes(s) to collect all declared objects in  a  list.
  546. They  make use of functions from an external data type.  mNoObjects creates an
  547. empty list, mObject adds a description of an object to a list, and  IsDeclared
  548. checks  for  multiple declarations. The latter function is used in a condition
  549. (CHECK) that issues an error message in case of multiple declarations.
  550.  
  551.      The abstract type SCOPE describes scopes such as  blocks  or  procedures.
  552. The  attribute Env (for environment) which is inherited from the abstract type
  553. ENV describes the set of objects that is visible at  certain  locations  in  a
  554. program.  Multiple  inheritance is expressed by writing an arrow <- and a list
  555. of abstract (base) types behind a type.  A scope is supposed to  reside  in  a
  556. surrounding  environment described by the attribute Env and to introduce a new
  557. set of declarations represented by the attribute Objects.  It computes  a  new
  558. environment  attribute  NewEnv valid inside this scope by calling the external
  559. function mEnv.  The computation of the attribute Objects is a dummy to satisfy
  560. the completeness requirement of attribute grammars.
  561.  
  562.      The abstract type USE describes the application or use of objects. A con-
  563. struct  that  uses  an  object  has  an attribute giving the identifier of the
  564. object (Ident).  This construct possesses an environment  attribute  Env  that
  565. describes  all objects visible at this construct. The attribute Object is used
  566. to refer to the symbol table entry of the used object. The  external  function
  567. Identify  takes  the  attributes  Ident  and Env as arguments and computes the
  568. attribute Object.  In case of the use of an undeclared  identifier  the  CHECK
  569. statement will issue an appropriate error message.
  570.  
  571.      The attribute definitions in Example 3 use a few keywords. These  associ-
  572. ate  so-called  properties with the attributes.  IN characterizes input attri-
  573. butes that have already a value when attribute evaluation starts. The value is
  574. usually  supplied  during  tree construction.  OUT characterizes output attri-
  575. butes whose value is needed after attribute evaluation.  Those attributes  may
  576. not  be removed from the tree nodes by an optimizer.  SYN and INH classify the
  577. attributes as synthesized and ancestral.
  578.  
  579.  
  580.  
  581.  
  582.  
  583.  
  584.  
  585.  
  586.  
  587.  
  588.                                                                              8
  589.  
  590.  
  591.      Example 4 shows the connection of the  abstract  symbol  table  with  the
  592. abstract  syntax  of the language MiniLAX. The subset of the node type defini-
  593. tions relevant for the symbol table problem is given. Whereas  abstract  types
  594. are introduced with the symbol := the character = is used for node types.
  595.  
  596.      A concrete list of declarations is described by the node type Decls which
  597. is a subtype of the abstract type DECLS.  A single declaration is described by
  598. the node type Decl which inherits from DECL.  Two specializations are  derived
  599. from  the  node  type Decl describing two kinds of declarations: variables and
  600. procedures (Var and Proc).  Through inheritance from DECL every Decl specifies
  601. already an identifier (attributes Ident and Pos) and a reference to a succeed-
  602. ing declaration (attribute Next).  Therefore the specializations have just  to
  603. add  the  missing  components  which is a description of the type in case of a
  604. variable and the formal parameters, the local declarations, and the  procedure
  605. body (Formals, Decls, Stats) in case of a procedure.
  606.  
  607.     Example 4:
  608.     MODULE AbstractSyntax
  609.     MiniLax            = Proc .
  610.     Decls <- DECLS     = <
  611.        NoDecl          = .
  612.        Decl <- DECL    = <
  613.           Var          = Type .
  614.           Proc         = Formals Decls Stats .
  615.        > .
  616.     > .
  617.     Stats              = <
  618.        NoStat          = .
  619.        Stat            = Next: Stats <
  620.           Assign       = Adr Expr            [Pos: tPosition] .
  621.           Call <- USE  = Actuals             [Pos: tPosition] .
  622.           If           = Expr Then: Stats Else: Stats .
  623.           While        = Expr Stats .
  624.           Read         = Adr .
  625.           Write        = Expr .
  626.        > .
  627.     > .
  628.     Expr               =                     [Pos: tPosition] <
  629.        Binary          = Lop: Expr Rop: Expr [Operator: SHORTCARD] .
  630.        Unary           = Expr                [Operator: SHORTCARD] .
  631.        IntConst        =                     [Value: INTEGER] .
  632.        RealConst       =                     [Value: REAL   ] .
  633.        BoolConst       =                     [Value: BOOLEAN] .
  634.        Adr             = <
  635.           Index        = Adr Expr .
  636.           Ident <- USE = .
  637.        > .
  638.     > .
  639.     END AbstractSyntax
  640.  
  641.  
  642.  
  643.  
  644.  
  645.  
  646.  
  647.  
  648.  
  649.  
  650.  
  651.  
  652.                                                                              9
  653.  
  654.  
  655.      The language knows two locations where objects are used: at  a  procedure
  656. call  and  at  a variable occurring in an expression. Therefore the node types
  657. Call and Ident are subtypes of the abstract type USE.  The node type Call spe-
  658. cializes  the  usage of an object by adding a list of actual parameters and an
  659. attribute Pos which is needed for an error message.
  660.  
  661.      The attribute computations in  the  attribute  grammar  for  MiniLAX  are
  662. grouped  into  modules (see Example 5). We present excerpts from three modules
  663. that are involved in the symbol table problem. The part of  the  module  Decls
  664. shown in Example 5 specializes the computation of the attribute Next:ObjectsIn
  665. for the concrete declarations of the language. This way the information in the
  666. symbol table is extended by the kind of the declared object, the type of vari-
  667. ables, and the formal parameters of procedures.
  668.  
  669.      The module named Env  specifies  all  computations  for  the  environment
  670. attribute.   It  is  reproduced  completely. All node types whose subtrees can
  671. contain applications of objects need an environment attribute Env  and  become
  672. therefore  subtypes of the abstract type ENV: Decls, Stats, Actuals, and Expr.
  673. The first attribute computation of  Proc  connects  the  "interfaces"  of  the
  674. abstract  types  DECLS and SCOPES.  The attribute Decls:ObjectsOut is the col-
  675. lected list of locally declared objects.  It  is  assigned  to  the  attribute
  676. Objects  which  is required to hold this information from the point of view of
  677.  
  678.     Example 5:
  679.     MODULE Decls
  680.     Proc           = { Next:ObjectsIn := mProc (ObjectsIn, Ident, Formals); } .
  681.     Var            = { Next:ObjectsIn := mVar  (ObjectsIn, Ident, Type);    } .
  682.     END Decls
  683.     MODULE Env
  684.     Decls   <- ENV = .
  685.     Stats   <- ENV = .
  686.     Actuals <- ENV = .
  687.     Expr    <- ENV = .
  688.     MiniLax        = { Proc:Env  := NoEnv           ; } .
  689.     DECL          := { Next:Env  := NoEnv           ; } .
  690.     Decl           = { Next:Env  := Env             ; } .
  691.     Proc <- SCOPE  = { Objects   := Decls:ObjectsOut;
  692.                        Stats:Env := NewEnv          ;
  693.                        Decls:Env := NewEnv          ; } .
  694.     END Env
  695.     MODULE Conditions
  696.     Call           = { CHECK IsObjectKind (Object, Proc)
  697.                        ==> Error ("only procedures can be called", Pos); } .
  698.     Ident          = { CHECK IsObjectKind (Object, Var)
  699.                        ==> Error ("variable required"            , Pos); } .
  700.     END Conditions
  701.  
  702.  
  703.  
  704.  
  705.  
  706.  
  707.  
  708.  
  709.  
  710.  
  711.  
  712.  
  713.                                                                             10
  714.  
  715.  
  716. the abstract type SCOPE.  SCOPE computes an attribute  NewEnv  describing  the
  717. objects visible inside the procedure. The value of this attribute is passed to
  718. the attributes Stats:Env and Decls:Env to make the environment  available  for
  719. the components of the procedure.  The rules given in the module Env suffice to
  720. specify all computations necessary for the  environment  attribute.  The  many
  721. missing rules are inserted automatically by the tool ag as simple copy rules.
  722.  
  723.      Finally, the module Conditions adds checks to the locations where objects
  724. are  used.  The abstract type USE already checks whether an object is declared
  725. or not. We still need to check if an object is of the right kind. This test is
  726. performed by the external procedure IsObjectKind.
  727.  
  728. 6.  Comparison
  729.  
  730.      This section compares object-oriented attribute grammars as introduced in
  731. this  paper  with  the  well-known  concepts of (attribute) grammars, tree and
  732. record types, type extensions, and object-oriented programming.  The  goal  is
  733. to  reveal  the  common properties as well as the differences among these con-
  734. cepts. These areas are related because of  the  following  reasons:  attribute
  735. grammars  are  usually  based  on  context-free grammars. An attribute grammar
  736. specifies an evaluation of attributes of a tree defined by such a context-free
  737. grammar.   Trees  can  be implemented using a set of record type declarations.
  738. Therefore context-free grammars, trees, and record types  deal  more  or  less
  739. with  the same concept. Table 1 compares the most important notions from these
  740. areas. Additionally we included the notions from the area  of  object-oriented
  741. (oo) programming as described e. g. in [Bla89].
  742.  
  743.  
  744. __________________________________________________________________________________________
  745.  (attribute) grammars    trees                  types                   oo-programming
  746. __________________________________________________________________________________________
  747.  rule                    node type              record type             class
  748.  attribute               field in a node type   record field            instance variable
  749.  nonterminal             set of node types      union of record types   -
  750.  terminal                distinct node type     record type without     -
  751.                                                    pointer fields
  752.  rule application        tree node              record variable         object, instance
  753.  attribute computation   -                      procedure declaration   method
  754.  -                       -                      procedure call          message
  755.  -                       -                      base type               superclass
  756.  -                       -                      derived type            subclass
  757.  -                       -                      extension               inheritance
  758. __________________________________________________________________________________________
  759.  
  760.  
  761.  
  762.  
  763.  
  764.  
  765.  
  766.  
  767.  
  768.  
  769.  
  770.  
  771.                       
  772.  
  773.  
  774.  
  775.  
  776.  
  777.  
  778.  
  779.  
  780.  
  781.  
  782.  
  783.                                              
  784.  
  785.  
  786.  
  787.  
  788.  
  789.  
  790.  
  791.  
  792.  
  793.  
  794.  
  795.                                                                      
  796.  
  797.  
  798.  
  799.  
  800.  
  801.  
  802.  
  803.  
  804.  
  805.  
  806.  
  807.                                                                                          
  808.  
  809.  
  810.  
  811.  
  812.  
  813.  
  814.  
  815.  
  816.  
  817.  
  818.  
  819.  
  820.  
  821. Table 1: Comparison of notions from the areas of grammars, trees, types, and oo-programming
  822.  
  823.  
  824.      Object-oriented attribute grammars are missing in Table 1.  For  them  we
  825. used the notions from attribute grammars and added the notions node type, base
  826. type, subtype or derived type, and inheritance from the other areas.
  827.  
  828.  
  829.  
  830.  
  831.  
  832.  
  833.  
  834.  
  835.  
  836.  
  837.  
  838.  
  839.  
  840.                                                                             11
  841.  
  842.  
  843. 6.1.  Attribute Grammars
  844.  
  845.      Conventional grammars in BNF allow several productions with the same non-
  846. terminal  symbol  on the left-hand side. A node type in object-oriented attri-
  847. bute grammars, which corresponds to a nonterminal as well as to a  rule  name,
  848. has  exactly  one right-hand side.  The selector names can be regarded as syn-
  849. tactic sugar.  To allow for several different derivations, a subtype  relation
  850. between node types is added.  During a derivation, a node type may be replaced
  851. by its right-hand side or by a subtype.  Inheritance is a notation  to  factor
  852. out  parts  that  are  common  to several node types such as right-hand sides,
  853. attributes, and attribute computations.  Fortunately, attributes  local  to  a
  854. rule (node type) are possible without any special construct.
  855.  
  856.      Object-oriented attribute grammars are a notation to write  BNF  grammars
  857. in  a  short  and  concise  way and where the underlying tree structure can be
  858. exactly described. With respect to  attribute  grammars  the  same  notational
  859. advantages  hold.   Attribute  grammars  are a special case of object-oriented
  860. attribute grammars. They are characterized by a one level  subtype  hierarchy,
  861. right-hand sides and attribute computations are defined for subtypes only, and
  862. attributes are associated only with base types.  In terms of attribute grammar
  863. classes  or attribute grammar semantics object-oriented attribute grammars are
  864. equivalent to attribute grammars.
  865.  
  866. 6.2.  Trees and Records
  867.  
  868.      When trees are stored in  memory,  they  can  be  represented  by  linked
  869. records.  Every node type corresponds to a record type. Object-oriented attri-
  870. bute grammars directly describe the structure of attributed syntax trees.  The
  871. node  types can be seen as record types. The right-hand side elements resemble
  872. pointer valued fields describing the tree structure  and  the  attributes  are
  873. additional  fields  for  arbitrary information stored at tree nodes. The field
  874. name and field type needed for record types are also present in the node types
  875. of object-oriented attribute grammars.
  876.  
  877. 6.3.  Type Extensions
  878.  
  879.      Type extensions have been introduced with the language  Oberon  by  Wirth
  880. [Wir88a, Wir88b, Wir88c].  They allow the definition of a record type based on
  881. an existing record type by adding  record  fields.  This  extension  mechanism
  882. induces  a  subtype relation between record types. The subtype and inheritance
  883. features are equivalent in object-oriented attribute grammars and type  exten-
  884. sions  with  the  difference  that  Wirth  uses the word extension in place of
  885. inheritance and restricts it to single inheritance.
  886.  
  887. 6.4.  Object-Oriented Programming
  888.  
  889.      The concepts of subtype  and  inheritance  in  object-oriented  attribute
  890. grammars  and  object-oriented  programming  have  many  similarities and this
  891. explains the name object-oriented  attribute  grammars.   The  notions  class,
  892. instance  variable, object, superclass, and subclass have direct counter parts
  893. (see Table 1).  There are also some differences.  Object-oriented  programming
  894. allows  an arbitrary number of named methods which are activated by explicitly
  895. sending messages. In object-oriented attribute grammars there is  exactly  one
  896.  
  897.  
  898.  
  899.  
  900.  
  901.  
  902.  
  903.  
  904.  
  905.  
  906.                                                                             12
  907.  
  908.  
  909. attribute  computation  for  an  attribute. This computation corresponds to an
  910. unnamed method.  There is nothing like messages: The attribute computation for
  911. an attribute is activated implicitly and exactly once.
  912.  
  913. 7.  Summary
  914.  
  915. We presented object-oriented  attribute  grammars  with  single  and  multiple
  916. inheritance.  The distinction between abstract types and node types allows for
  917. a restricted form of multiple inheritance that can still be implemented  effi-
  918. ciently.  The  nonterminals  or  node  types are the entities constituting the
  919. inheritance hierarchy. The items that are subject to  inheritance  are  right-
  920. hand side elements, attributes, and attribute computations.
  921.  
  922.      Object-oriented attribute grammars are a compact  and  flexible  notation
  923. for  language specifications. The repetition of information is avoided as com-
  924. mon parts can be factored out. The reuse of definitions  is  supported  -  new
  925. definitions can be derived from existing ones by specializations.
  926.  
  927.      We extended the attribute  evaluator  generator  ag  to  process  object-
  928. oriented  attribute  grammars with multiple inheritance. It turned out that it
  929. is possible to generate efficient attribute evaluators for this kind of attri-
  930. bute grammars.
  931.  
  932.      While we are very satisfied with the advantages of single inheritance  we
  933. have  just  started  to  explore  the feasibility of multiple inheritance. Our
  934. current goal is to build a collection of attribute grammar modules  containing
  935. abstract  types  that model concepts of programming languages such as the dis-
  936. cussed symbol table. Together with abstract data types  these  will  result  a
  937. library  of  reusable  parts oriented towards semantic analysis of programming
  938. languages. If possible those parts will be  designed  to  specify  aspects  of
  939. semantic analysis independent of concrete languages.
  940.  
  941. References
  942.  
  943. [Bla89]
  944.      G.  Blaschek,  Implementation  of   Objects   in   Modula-2,   Structured
  945.      Programming 10, 3 (1989), 147-155.
  946.  
  947. [Gro89]
  948.      J. Grosch, Ag - An Attribute  Evaluator  Generator,  Compiler  Generation
  949.      Report  No.  16,  GMD Forschungsstelle an der Universitat Karlsruhe, Aug.
  950.      1989.
  951.  
  952. [Gro90a]
  953.      J. Grosch, Object-Oriented Attribute  Grammars,  in  Proceedings  of  the
  954.      Fifth International Symposium on Computer and Information Sciences (ISCIS
  955.      V), A. E. Harmanci and E. Gelenbe (ed.),  Cappadocia,  Nevsehir,  Turkey,
  956.      Oct. 1990, 807-816.
  957.  
  958. [Gro90b]
  959.      J. Grosch, Specification of a Minilax  Interpreter,  Compiler  Generation
  960.      Report  No.  22,  GMD Forschungsstelle an der Universitat Karlsruhe, Mar.
  961.      1990.
  962.  
  963.  
  964.  
  965.  
  966.  
  967.  
  968.  
  969.  
  970.  
  971.  
  972.                                                                             13
  973.  
  974.  
  975. [GrE90]
  976.      J. Grosch and H. Emmelmann, A Tool Box for  Compiler  Construction,  LNCS
  977.      477, (Oct. 1990), 106-116, Springer Verlag.
  978.  
  979. [Hed89]
  980.      G. Hedin, An Object-Oriented Notation for Attribute  Grammars,  Proc.  of
  981.      the  European  Conference  on  Object-Oriented  Programming  (ECOOP '89),
  982.      Nottingham, 1989, 329-345.
  983.  
  984. [Knu68]
  985.      D. E. Knuth, Semantics of Context-Free  Languages,  Mathematical  Systems
  986.      Theory 2, 2 (June 1968), 127-146.
  987.  
  988. [Knu71]
  989.      D.  E.  Knuth,   Semantics   of   Context-free   Languages:   Correction,
  990.      Mathematical Systems Theory 5, (Mar. 1971), 95-96.
  991.  
  992. [Kos91]
  993.      K. Koskimies, Object-Orientation in Attribute Grammars, LNCS 545, (1991),
  994.      297-329, Springer Verlag.
  995.  
  996. [Wir88a]
  997.      N. Wirth, Type Extensions, ACM Trans. Prog. Lang. and Systems 10, 2 (Apr.
  998.      1988), 204-214.
  999.  
  1000. [Wir88b]
  1001.      N. Wirth, From Modula to Oberon, Software-Practice  &  Experience  18,  7
  1002.      (July 1988), 661-670.
  1003.  
  1004. [Wir88c]
  1005.      N. Wirth, The Programming Language Oberon, Software-Practice & Experience
  1006.      18, 7 (July 1988), 671-690.
  1007.  
  1008.  
  1009.  
  1010.  
  1011.  
  1012.  
  1013.  
  1014.  
  1015.  
  1016.  
  1017.  
  1018.  
  1019.  
  1020.  
  1021.  
  1022.  
  1023.  
  1024.  
  1025.  
  1026.  
  1027.  
  1028.  
  1029.  
  1030.  
  1031.  
  1032.  
  1033.  
  1034.  
  1035.  
  1036.  
  1037.                                                                              1
  1038.  
  1039.  
  1040. Contents
  1041.  
  1042.         Abstract ........................................................    1
  1043.         Keywords ........................................................    1
  1044. 1.      Introduction ....................................................    1
  1045. 2.      Single Inheritance ..............................................    3
  1046. 3.      Example .........................................................    4
  1047. 4.      Multiple Inheritance ............................................    5
  1048. 5.      Example .........................................................    6
  1049. 6.      Comparison ......................................................   10
  1050. 6.1.    Attribute Grammars ..............................................   11
  1051. 6.2.    Trees and Records ...............................................   11
  1052. 6.3.    Type Extensions .................................................   11
  1053. 6.4.    Object-Oriented Programming .....................................   11
  1054. 7.      Summary .........................................................   12
  1055.         References ......................................................   12
  1056.  
  1057.  
  1058.  
  1059.  
  1060.  
  1061.  
  1062.  
  1063.  
  1064.  
  1065.  
  1066.  
  1067.  
  1068.  
  1069.  
  1070.  
  1071.  
  1072.  
  1073.  
  1074.  
  1075.  
  1076.  
  1077.  
  1078.  
  1079.  
  1080.  
  1081.  
  1082.  
  1083.  
  1084.  
  1085.  
  1086.  
  1087.  
  1088.  
  1089.  
  1090.  
  1091.  
  1092.  
  1093.  
  1094.  
  1095.  
  1096.  
  1097.  
  1098.